#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/9/20 22:58
# @Author  : Yuyun
# @File    : 根据单个节点信息构造二叉树and给出遍历信息.py
# @IDE     : PyCharm


"""
题目包含多行输入，第一行为一个整数 N，表示二叉树的节点总数，后面将有 N 行对应于二叉树的 N 个节点的信息。

每行的数据格式遵循如下规则：

每行开始是该节点的标识符，代表二叉树中具体的一个节点。

节点标识符之后是两个数字，分别表示该节点的左孩子和右孩子的序号。序号根据输入顺序从 1 开始自动分配，即第一个输入的节点序号为 1，第二个为 2，以此类推。

若某个节点的左孩子或右孩子序号为 0，则表示该节点不存在相应的左孩子或右孩子。
"""
class TreeNode:
    def __init__(self, val, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def buildtree(self,node_info_list:set) -> TreeNode:
        if not node_info_list:
            return None
        node_list = []
        #   单独实例化每个节点，存储到节点列表中
        for node_info in node_info_list:
            node = TreeNode(node_info[0])
            node_list.append(node)
        #   从0开始填充左右孩子
        for j in range(len(node_list)):
            #   节点左孩子和右孩子的序号，由于序号从1开始，故nodelist定位时 - 1
            left_index = int(node_info_list[j][1])
            right_index = int(node_info_list[j][2])
            if left_index != 0:
                node_list[j].left = node_list[left_index - 1]
            if right_index != 0:
                node_list[j].right = node_list[right_index - 1]
        return node_list[0]

    def preorder_traversal(self, root: TreeNode, res=None):
        if res is None:
            res = []
        if root:
            res.append(root.val)
            res = self.preorder_traversal(root.left, res)
            res = self.preorder_traversal(root.right, res)
        return res

    def midorder_traversal(self, root: TreeNode, res=None):
        if res is None:
            res = []
        if root:
            res = self.midorder_traversal(root.left, res)
            res.append(root.val)
            res = self.midorder_traversal(root.right, res)
        return res

    def postorder_traveral(self, root: TreeNode, res=None):
        if res is None:
            res = []
        if root:
            res = self.postorder_traveral(root.left, res)
            res = self.postorder_traveral(root.right, res)
            res.append(root.val)
        return res

if __name__ == '__main__':
    try:
        n = int(input())
        node_info_list = []
        for _ in range(n):
            node_info = list(map(str, input().split()))
            node_info_list.append(node_info)
        solution = Solution()
        root = solution.buildtree(node_info_list)

        res_pr = solution.preorder_traversal(root)
        print(''.join(res_pr))
        res_pr.clear()
        res_pr = solution.midorder_traversal(root)
        print(''.join(res_pr))
        res_pr.clear()
        res_pr = solution.postorder_traveral(root)
        print(''.join(res_pr))
        res_pr.clear()

    except:
        pass